package dfs;

import java.util.Stack;

/**
 * @author pengfei.hpf
 * @date 2020/3/5
 * @verdion 1.0.0
 * 在二维平面上，我们将石头放置在一些整数坐标点上。每个坐标点上最多只能有一块石头。
 *
 * 现在，move 操作将会移除与网格上的某一块石头共享一列或一行的一块石头。
 *
 * 我们最多能执行多少次 move 操作？
 *
 *  
 *
 * 示例 1：
 *
 * 输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
 * 输出：5
 * 示例 2：
 *
 * 输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
 * 输出：3
 * 示例 3：
 *
 * 输入：stones = [[0,0]]
 * 输出：0
 *  
 *
 * 提示：
 *
 * 1 <= stones.length <= 1000
 * 0 <= stones[i][j] < 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RemoveStones {
    //TODO: 邻接矩阵表示方式
    public int removeStones(int[][] stones){
        if(stones == null || stones.length <= 1){
            return 0;
        }
        int n = stones.length;
        int[][] board = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = i +1; j < n; j ++){
                if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]){
                    board[i][++board[i][0]] = j;
                    board[j][++board[j][0]] = i;
                }
            }
        }
        int res = 0;
        boolean[] seen = new boolean[n];
        for(int i = 0; i < n; i++){
            if(!seen[i]){
                Stack<Integer> stack = new Stack<>();

                stack.push(i);
                res --;
                seen[i] = true;
                while(!stack.isEmpty()){
                    int pos = stack.pop();

                    res ++;
                    for(int j = 1; j <= board[pos][0]; j ++){
                        if(!seen[board[pos][j]]){
                            stack.push(board[pos][j]);
                            seen[board[pos][j]] = true;
                        }
                    }
                }
            }

        }
        return res;

    }
}
